package com.guang.guiji.sort;

public class FASTEST_WAY {
	public static final int M = 2;

	// 不使用0和(0,0)的位置，使程序更直观
	public static void FASTEST_WAY(float a[][], float t[][], float e[],
			int x[], int n) {

		int[][] l = new int[M + 1][n + 1];// 定义l[i][j]为装配线的编号（1或2），其中的装配站j-1被通过的装配站S[i][j]的最快路线使用
		float[][] f = new float[M + 1][n + 1];
		int l_last = 0;
		float f_last = 0;
		// 赋初值
		f[1][1] = e[1] + a[1][1];
		f[2][1] = e[2] + a[2][1];

		for (int j = 2; j <= n; j++) {
			if ((f[1][j - 1] + a[1][j]) <= (f[2][j - 1] + t[2][j - 1] + a[1][j])) {
				f[1][j] = f[1][j - 1] + a[1][j];
				l[1][j] = 1;
			} else {
				f[1][j] = f[2][j - 1] + t[2][j - 1] + a[1][j];
				l[1][j] = 2;
			}
			if ((f[2][j - 1] + a[2][j]) <= (f[1][j - 1] + t[1][j - 1] + a[2][j])) {
				f[2][j] = f[2][j - 1] + a[2][j];
				l[2][j] = 2;
			} else {
				f[2][j] = f[1][j - 1] + t[1][j - 1] + a[2][j];
				l[2][j] = 1;
			}
		}

		System.out.println("The shortest length is:");
		if ((f[1][n] + x[1]) <= (f[2][n] + x[2])) {
			f_last = f[1][n] + x[1];
			l_last = 1;
		} else {
			f_last = f[2][n] + x[2];
			l_last = 2;
		}
		System.out.println(f_last);
		
		//输出步骤
		int i = l_last;
		System.out.println("the line: "+i);
		for (int j = n; j >= 2; j--) {
			i = l[i][j];
			System.out.println("the line: "+i);
		}

	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 6;
		float[][] a ={{},{0,7,9,3,4,8,4},{0,8,5,6,4,5,7}};
		float[][] t = {{},{0,2,3,1,3,4},{0,2,1,2,2,1}};
		float[] e ={0,2,4};
		int[] x = {0,3,2};
		FASTEST_WAY(a,t,e,x,n);
	}
}
